Міністерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра комп’ютерних наук
ЛАБОРАТОРНА РОБОТА №2
з дисципліни “Теорія алгоритмів”
Тема роботи: Структури алгоритмів.
Лабораторна робота №2
Тема роботи: Структури алгоритмів.
Мета роботи: Вивчення основних елементів структури обчислювальних алгоритмів.
Теоретичні відомості
Часто в інженерній практиці виникає необхідність порівняння технічних об(єктів. У цих випадках опис технічного об(єкта необхідно звести до таких математичних об(єктів як числа, вектори, матриці або функції. У цьому випадку порівнюютбся вже не самі об`єкти, а іх математичні представлення.
У таких випадках характерисртикою об(єктів є поняття норми, а самі об(єкти розглядають у відповідних метричних просторах, наприклад . Нормою в називається дійснозначна функція (позначають -норма Х), яка задовільняє такі умови:
для будь-якого , причому тільки якщо ;
для кожного і ;
для кожного ;
Найбільш поширені слідуючі норми:
для дійсних чисел: модуль числа ;
для комплексних чисел:
модуль комплексного числа
для векторів :
- норма (норма Чебишева) ;
- норма (Евклідова норма) ;
- норма ;
для матриць:
норма Фробеніуса ;
l1- норма ,
де - j-ий стовбець матриці X
для функцій:
, де T – интервал задання функції X(t).
Порівняння норм здійснюється так само як порівняння дійсних чисел.
В деяких випадках виникає необхідність
391
299
Знаходження спільної міри кількох об`єктів. У
299
1
цьому випадку поріввнюються значення
299
92
норми, а для знаходження найбільшого
276
3
спільного дільника (НСД) використовується
92
23
алгоритм Евкліда. Приклад знаходження НСД
92
4
за алгоритмом Евкліда представлено на рис.1. У цьому прикладі шукають НСД чисел
0
391 і 299. Значення НСД буде рівне останньому дільнику, після ділення на який остача рівна 0, тобто НСД рівне 23.
Рис.1
Для знаходження НСД трьох і більше чисел спочатку знаходять НСД будь-яких двох чисел а потім – знайденого НСД і одного з чисел що залишилися.
Завдання до лабораторної роботи.
Згідно заданого варіанту завдань написати програму на мові ПАСКАЛЬ або С++ і реалізувати її на ЕОМ.
Представити результати роботи програми.
Оформити звіт по виконаній роботі.
Зміст звіту
Звіт повинен містити:
Завдвння до роботи.
Блок-схему алгоритму та граф-схему алгоритму і їх порівняльний опис.
Текст програми.
Результати роботи.
Висновки.
Контрольні запитання
Основні елементи алгоритмів.
Представлення алгоритмів у вигляді граф-схем.
Основні норми математичних об(єктів.
Алгоритм Евкліда.
Варіанти завдань
№ варіанту
Завдання
1
Знайти НСД для норми функцій і на інтервалі (0;7).
2
Знайти НСД чисел: 329868, 295596, 942123, 2984520, 409479.
3
Знайти НСД модулів комплексних чисел: 18564-13923j,
1080-1440j, 7533+10044j.
4
Знайти комплексне число, через яке можна виразити числа1915056+558558j і 3682200+1073975j використовуючи цілий множник, якщо це можливо.
5
Знайти НСД норм Чебишева векторів (12098,17952,119,3987,13) i (8794,1372,0,8892,6565).
6
Знайти спільну міру довжини векторів (5984,2992,1496,2992) i (741,1482,1482,2964).
7
Знайти спільну міру відстані між точками А1(345,921), А2(7209,2923) i B1(-987,352), B2(2685,1423).
8
Знайти вектор найбільшої довжини, через який можна виразити вектори (980343,508326,217854) і (72036,37352,17008).
9
Знайти НСД для норми Фробеніуса матриць:
і
10
Знайти НСД для l1- норми матриць:
i
Рекомендована література
Яворський Б.І. Математичні основи радіоелектроніки. ч.2.
Колмогоров. Фомин. Функциональный анализ.
3. Березина Л.Ю. Графы и их применение. М.: Просвещение, 01/01/79.
4. Кузнецов О.П., Адельсон-Вальский Г.М. Дискретная математика для нженера. М.: Энергия, 01/01/80, 344.
